# -*- encoding: utf-8 -*-


def counting_sort(collection):
    """
    params：
        collection为未排序的list
    排序过程：
        1. 创建计数list，下标为collection的数据范围，值为对应下标数据的个数
        2. 将计数list顺序求和
        3. 创建排序list，遍历collection，找到其在计数list中对应下标的值，即为排序list的位置，计数list中对应的值减 1
    """
    if not collection:
        return collection

    coll_len = len(collection)
    coll_max = max(collection)
    coll_min = min(collection)

    counting_arr_len = coll_max - coll_min + 1
    counting_arr = [0] * counting_arr_len
    for value in collection:
        counting_arr[value - coll_min] += 1

    for i in range(1, counting_arr_len):
        counting_arr[i] += counting_arr[i - 1]

    order = [0] * coll_len
    for value in collection:
        order[counting_arr[value - coll_min] - 1] = value
        counting_arr[value - coll_min] -= 1

    return order


def counting_sort_string(string):
    collection = [ord(x) for x in string]
    return ''.join([chr(x) for x in counting_sort(collection)])


if __name__ == '__main__':
    print(counting_sort([2, 5, 3, 0, 2, 3, 0, 3]))
    print(counting_sort_string('thisisthestring'))
